import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 * User: Roman
 * Date: 11.09.12
 * Time: 21:27
 * To change this template use File | Settings | File Templates.
 */
public class Board {
    private int[][] blocks;
    private int N;

    public Board(int[][] blocks) {
        N = blocks.length;
        this.blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                this.blocks[i][j] = blocks[i][j]; //Чи буде immutable?
        //        previous.moves++;
    }

    public int dimension() {
        return N;
    }

    public int hamming() {
        int hamming = 0;
        for (int i = 0; i < N * N - 1; i++)
            if (blocks[i / N][i % N] != i + 1)
                hamming++;
        return hamming;// + previous.moves + 1;   //що робити з previous і взагалі як працює nasted class?
    }

    public int manhattan() {
        int manhattan = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (blocks[i][j] > 0)
                    manhattan += Math.abs(i - (blocks[i][j] - 1) / N) + Math.abs(j - (blocks[i][j] - 1) % N);
        return manhattan; //+ previous.moves + 1; //що робити з previous і взагалі як працює nasted class?
    }

    public boolean isGoal() {
        for (int i = 0; i < N * N - 1; i++)
            if (blocks[i / N][i % N] != i + 1)
                return false;
        return true;
    }

    public Board twin() {
        int[][] tempGrid = new int[N][N];
        int temp;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                tempGrid[i][j] = blocks[i][j];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 1; j++)
                if ((blocks[i][j] != 0) && (blocks[i][j + 1] != 0)) {
                    temp = tempGrid[i][j];
                    tempGrid[i][j] = tempGrid[i][j + 1];
                    tempGrid[i][j + 1] = temp;
                    return new Board(tempGrid);
                }
        }
        return null;
    }

    public boolean equals(Object y) {
        if (y == this)
            return true;
        if (y == null)
            return false;
        if (this.getClass() != y.getClass())
            return false;
        Board x = (Board) y;
        if (x.N != N)
            return false;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (blocks[i][j] != x.blocks[i][j])
                    return false;
        return true;
    }

    public Iterable<Board> neighbors() {
        Stack<Board> neighbors = new Stack<Board>();
        int xPositionZero = 0, yPositionZero = 0;
        int[][] tempGrid = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                tempGrid[i][j] = blocks[i][j];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (blocks[i][j] == 0) {
                    xPositionZero = i;
                    yPositionZero = j;
                    break;
                }
        if ((xPositionZero - 1 >= 0)) {
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero - 1][yPositionZero];
            tempGrid[xPositionZero - 1][yPositionZero] = blocks[xPositionZero][yPositionZero];
            neighbors.push(new Board(tempGrid));
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero];
            tempGrid[xPositionZero - 1][yPositionZero] = blocks[xPositionZero - 1][yPositionZero];
        }

        if ((xPositionZero + 1 < N)) {
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero + 1][yPositionZero];
            tempGrid[xPositionZero + 1][yPositionZero] = blocks[xPositionZero][yPositionZero];
            neighbors.push(new Board(tempGrid));
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero];
            tempGrid[xPositionZero + 1][yPositionZero] = blocks[xPositionZero + 1][yPositionZero];
        }

        if ((yPositionZero + 1 < N)) {
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero + 1];
            tempGrid[xPositionZero][yPositionZero + 1] = blocks[xPositionZero][yPositionZero];
            neighbors.push(new Board(tempGrid));
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero];
            tempGrid[xPositionZero][yPositionZero + 1] = blocks[xPositionZero][yPositionZero + 1];
        }

        if ((yPositionZero - 1 >= 0)) {
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero - 1];
            tempGrid[xPositionZero][yPositionZero - 1] = blocks[xPositionZero][yPositionZero];
            neighbors.push(new Board(tempGrid));
            tempGrid[xPositionZero][yPositionZero] = blocks[xPositionZero][yPositionZero];
            tempGrid[xPositionZero][yPositionZero - 1] = blocks[xPositionZero][yPositionZero - 1];
        }

        return neighbors;
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(N + "\n");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                s.append(String.format("%2d ", blocks[i][j]));
            }
            s.append("\n");
        }
        return s.toString();
    }
}
